package pers.tz.题目.leetcode.树;

import pers.tz.common.TreeNode;

/**
 * @author irony
 * @date 2024-03-13
 */
public class leetcode_0236_二叉树的最近公共祖先 {
// 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
//
// 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，
// 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
    public static void main(String[] args) {

    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root, p, q).ans;
    }

    public static Info process(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return new Info(false, false, null);
        }

        Info left = process(root.left, p, q);
        Info right = process(root.right, p, q);

        boolean findP = root == p || left.findP || right.findP;
        boolean findQ = root == q || left.findQ || right.findQ;

        TreeNode ans = null;
        if (left.ans != null) {
            ans = left.ans;
        } else if (right.ans != null) {
            ans = right.ans;
        } else {
            if (findP && findQ) {
                ans = root;
            }
        }

        return new Info(findP, findQ, ans);
    }

    // 1. 是否找到P
    // 2. 是否找到Q
    // 3. 是否找到祖先
    public static class Info {
        public boolean findP;
        public boolean findQ;
        public TreeNode ans;
        public Info(boolean findP, boolean findQ, TreeNode ans) {
            this.findP = findP;
            this.findQ = findQ;
            this.ans = ans;
        }
    }
}
